package LeetCode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:53
 */
public class LeetCode210 {

    public static void main(String[] args) {
        int[][] prerequistites = {
                {1,0},
                {2,0},
                {3,1},
                {3,2}
        };
        int numCourses = 4;
        System.out.println(Arrays.toString(new LeetCode210().findOrder(numCourses, prerequistites)));
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0){
            return new int[0];
        }
        //算出每个点的入度
        int[] inDegrees = new int[numCourses];
        for (int[] p : prerequisites) {
            inDegrees[p[0]]++;
        }
        //将入度为0的放入启动队列中
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegrees.length; i++){
            if (inDegrees[i] == 0){
                queue.offer(i);
            }
        }

        //进行正式的判断
        int[] res = new int[numCourses];
        int count = 0;
        for (int i = 0; i < numCourses; i++){
            while (!queue.isEmpty()){
                int curr = queue.poll();
                res[count++] = curr;
                for (int[] p : prerequisites) {
                    if (p[1] == curr){//找到对应的点
                        //将对应的入度和边删除
                        inDegrees[p[0]]--;
                        if (inDegrees[p[0]] == 0){
                            queue.offer(p[0]);
                        }
                    }
                }
            }
        }
        if (count == numCourses){
            return res;
        }
        return new int[0];
    }
}
